package Elementary_algorithm.DynamicProgramming;

import org.junit.Test;

/*
最大子序和
给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
子数组 是数组中的一个连续部分。

示例 1：
输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组[4,-1,2,1] 的和最大，为6 。
示例 2：
输入：nums = [1]
输出：1
示例 3：
输入：nums = [5,4,-1,7,8]
输出：23

提示：
1 <= nums.length <= 105
-104 <= nums[i] <= 104
进阶：如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的 分治法 求解。

作者：LeetCode
链接：https://leetcode.cn/leetbook/read/top-interview-questions-easy/xn3cg3/
 */
public class _03最大子序和 {

    @Test
    public void test() {
        System.out.println(sunSubArray(new int[]{-2, 1, -3, 4, -1, 2, 1, -5, 4}));
    }

    //官解：方法一：动态规划
    /*
    我们用f(i)代表以第i个数结尾的「连续子数组的最大和」，那么很显然我们要求的答案就是：max( 0≤i≤n−1 , {f(i)} )
    因此我们只需要求出每个位置的f(i)，然后返回f数组中的最大值即可。
    那么我们如何求f(i)呢？我们可以考虑nums[i]单独成为一段还是加入f(i−1)对应的那一段，
    这取决于nums[i]和f(i−1)+nums[i]的大小，我们希望获得一个比较大的，于是可以写出这样的动态规划转移方程：
    f(i) = max{f(i−1)+nums[i] , nums[i]}
    再加上滚动数组思想将空间O(n) 降低成 O(1)
     */
    //ps: 化繁为简
    // 题目求一个具有最大和的连续子数组，变量为数组的前端和后端
    // 就将他变成数组内以第i个数结尾的「连续子数组的最大和」，变量只有数组的前端 ，即判断是否可以与第i个数相连
    // 然后求f数组中的最大值
    public int sunSubArray(int[] nums) {
        int pre = 0;
        int[] function = new int[nums.length];
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] >= pre + nums[i]) {
                function[i] = nums[i];
            }else {
                function[i] = pre + nums[i];
            }
            max = Math.max(max,function[i]);
            pre = function[i];
        }
        return max;
    }
    //官方写法
    class Solution {
        public int maxSubArray(int[] nums) {
            int pre = 0, maxAns = nums[0];
            for (int x : nums) {
                pre = Math.max(pre + x, x);
                maxAns = Math.max(maxAns, pre);
            }
            return maxAns;
        }
    }


    //官解：方法二：分治
    // 作者：力扣官方题解
    // 链接：https://leetcode.cn/problems/maximum-subarray/solutions/228009/zui-da-zi-xu-he-by-leetcode-solution/
    //ps: 思路看链接
    // 分治是一种化繁为简
    // 与方法一的区别在于 化繁方式不同，方法一在于提出一个新的子问题，将子问题的答案收集起来获得真正问题的答案
    // 方法二则是将原本的问题变成更小型的原本问题，最终获得的的最小型的原子问题答案很容易思考，
    // 然后根据原问题维护原子问题的几个量信息，将其通过递归(可能不一定要采用递归？)的方式传回合并
    // 最终获得原问题的答案
    // Eg:我们定义一个操作 get(a, l, r)表示查询a序列[l,r]区间内的最大子段和，那么最终我们要求的答案就是get(nums, 0, nums.size() - 1)。
    // 如何分治实现这个操作呢？对于一个区间[l,r]，我们取m = (l+r)/2,对区间[l,m]和[m+1,r]分治求解。
    // 当递归逐层深入直到区间长度缩小为1的时候，递归「开始回升」。
    // 所以分治Step
    // 1.能否分治，怎么分治？
    // 2.要维护区间的哪些信息？
    // 3.如何合并这些信息？
    class Solution2 {
        public class Status {
            public int lSum, rSum, mSum, iSum;

            public Status(int lSum, int rSum, int mSum, int iSum) {
                this.lSum = lSum;
                this.rSum = rSum;
                this.mSum = mSum;
                this.iSum = iSum;
            }
        }

        public int maxSubArray(int[] nums) {
            return getInfo(nums, 0, nums.length - 1).mSum;
        }

        public Status getInfo(int[] a, int l, int r) {
            if (l == r) {
                return new Status(a[l], a[l], a[l], a[l]);
            }
            int m = (l + r) >> 1;
            Status lSub = getInfo(a, l, m);
            Status rSub = getInfo(a, m + 1, r);
            return pushUp(lSub, rSub);
        }

        public Status pushUp(Status l, Status r) {
            int iSum = l.iSum + r.iSum;
            int lSum = Math.max(l.lSum, l.iSum + r.lSum);
            int rSum = Math.max(r.rSum, r.iSum + l.rSum);
            int mSum = Math.max(Math.max(l.mSum, r.mSum), l.rSum + r.lSum);
            return new Status(lSum, rSum, mSum, iSum);
        }
    }




}
